package com.github.yangyishe.p500;

import java.util.ArrayList;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 * 方案2
 */
public class Problem438S2 {
    public static void main(String[] args) {
        String s="aaaaaaaaaa";
        String p="aaaaaaaaaaaaa";

        Problem438S2 problem438S2 = new Problem438S2();
        List<Integer> anagrams = problem438S2.findAnagrams(s, p);
        System.out.println("anagrams = " + anagrams);

    }

    /**
     * 思路：
     * 对于字符串p而言，顺序完全不重要。
     * 可以考虑将每个char给定一个hash值，则可计算出字符串p的哈希值之和。
     * 这之后，再使用双指针分别记录开头和结束索引，计算并遍历获取hash和
     *
     * 如果hash和相等，则认为是字母异位词，否则不是
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        if(s.length()<p.length()){
            return new ArrayList<>();
        }
        //1. 给每个char一个hash值
        int[] hashs=new int[26];
        for(int i=0;i<26;i++){
            hashs[i]=new Object().hashCode();
        }

        //2. 计算获取p的hash值和
        long phash=0;
        for(char c:p.toCharArray()){
            phash+=(hashs[c-'a']);
        }

        //3. 快慢指针计算获取s在每个位置的hash和
        List<Integer> resultList=new ArrayList<>();
        long shash=0;
        for(int i=0;i<p.length();i++){
            shash+=(hashs[s.charAt(i)-'a']);
        }
        if(shash==phash){
            resultList.add(0);
        }
        for(int i=1;i<=s.length()-p.length();i++){
            shash=shash-hashs[s.charAt(i-1)-'a']+hashs[s.charAt(i+p.length()-1)-'a'];
            if(shash==phash){
                resultList.add(i);
            }
        }

        return resultList;
    }
}
